import math


# class Solution(object):
#     def findIntegers(self, n):
#         k = int(math.log2(n)) + 1
#         self.ans = 0
#
#         def dfs(i, v, num):
#             if i == k:
#                 if num <= n:
#                     self.ans += 1
#             else:
#                 if v == 0:
#                     dfs(i + 1, 0, num * 2)
#                     dfs(i + 1, 1, num * 2 + 1)
#                 else:
#                     dfs(i + 1, 0, num * 2)
#
#         dfs(0, 0, 0)
#         return self.ans
import functools
import math
class Solution(object):
    def findIntegers(self, n):
        k = int(math.log2(n)) + 1
        @functools.cache
        def dfs(i):
            if i == 0:
                return 1
            if i == 1:
                return 2
            return dfs(i - 2) + dfs(i - 1)
        ans = 0
        last = 0
        for i in range(k - 1, -1, -1):
            if n & (1 << i):
                ans += dfs(i)
                if last:
                    break
                else:
                    last = 1
            else:
                last = 0
            if i == 0:
                ans += 1
        return ans





data = Solution()
n = 5
print(data.findIntegers(n))
